package Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Stack
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-21  10:21
 * @Description: TODO
 * @Version: 1.0
 */
public class 接雨水42 {

    // 时间复杂度：O(n²），遍历每一列需要n，找出左边最高和右边最高的墙加起来刚好又是一个n，所以是n²。
    // 空间复杂度：O(1）。


    //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
    public int trap(int[] height) {
        int sum = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }
            int max_right = 0;
            //找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }
            //找出两端较小的
            int min = Math.min(max_left, max_right);
            //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    public int trap2(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        // 获取从左边向右边的最大值
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        // 获取从右边边向左边的最大值
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        // 然后在计算积水的面积
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }

    // 采用单调栈的
    public int trap3(int[] height) {
        int ans = 0;
        // 构建单调递增加栈
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                // 由于的单调递增栈，那就第二个就是当前左边的第一个大于的元素 这个时候就是的栈顶的下表和元素
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}
